package com.dubious.interview.euler;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.joda.time.DateTime;

import com.dubious.interview.euler.prime.SievePrimeIterator;

/**
 * By replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43,
 * 53, 73, and 83, are all prime.
 * 
 * By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the
 * first example having seven primes among the ten generated numbers, yielding the family: 56003,
 * 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this
 * family, is the smallest prime with this property.
 * 
 * Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits)
 * with the same digit, is part of an eight prime value family.
 * 
 */
public class Problem51 {

    public static Map<Integer, List<Integer>> oneBits = new HashMap<Integer, List<Integer>>();
    static {
        for (int i = 1; i < 200; i++) {
            List<Integer> oneBitsForI = new ArrayList<Integer>();
            int value = i;
            int j = 0;
            while (value > 0) {
                if (value % 2 == 1) {
                    oneBitsForI.add(j);
                }
                j++;
                value = value / 2;
            }

            oneBits.put(i, oneBitsForI);
        }

        System.out.println(oneBits);
    }

    public static final int FAMILY_MEMBERS = 8;
    public static final int NUM_MISSES = 10 - FAMILY_MEMBERS;

    
    
    public static long run() {
        // assume the number is less than 1 million (so it has at most 6 digits).
        // we first calculate the primes under 1 million then we check each prime whether it matches
        // the criteria
        System.out.println("Start time: " + new DateTime());

        long upperBound = 1000000;
        Set<Long> primes = new LinkedHashSet<Long>();
        
        for(Long prime : new SievePrimeIterator(upperBound))
        {
            primes.add(prime);
        }

        // TODO: Remove
        // System.out.println("primes: " + primes);
        // isInPrimeFamily(100109L, primesAsSet);
        // isInPrimeFamily("56003", primesAsSet, oneBits.get(12));
        // TODO: End Remove

        Long lowestInPrimeFamily = 0L;
        for (Long prime : primes) {
            if (isInPrimeFamily(prime, primes)) {
                lowestInPrimeFamily = prime;
                break;
            }
        }

        if (lowestInPrimeFamily == 0L) {
            throw new RuntimeException("Could not find match with upperBound " + upperBound);
        }
        
        return lowestInPrimeFamily;
    }

    private static boolean isInPrimeFamily(Long prime, Set<Long> primes) {
        String primeAsString = prime.toString();
        int numDigits = primeAsString.length();
        // use binary "mask" to determine which digits to change
        int numIterations = (int) Math.pow(2, numDigits) - 1;
        for (int i = 1; i <= numIterations; i++) {
            List<Integer> oneBitsForI = oneBits.get(i);

            // we only want to treat combinations where the digits of value are the same
            char digit = primeAsString.charAt(oneBitsForI.get(0));
            boolean isSame = true;
            for (int j = 1; j < oneBitsForI.size(); j++) {
                if (primeAsString.charAt(oneBitsForI.get(j)) != digit) {
                    // the digits are not the same
                    isSame = false;
                    break;
                }
            }

            if (!isSame) {
                continue;
            }

            if (isInPrimeFamily(primeAsString, primes, oneBitsForI)) {
                return true;
            }
        }

        return false;
    }

    private static boolean isInPrimeFamily(
            String primeAsString,
            Set<Long> primes,
            List<Integer> oneBits) {
        int numMisses = 0;
        StringBuilder value = new StringBuilder(primeAsString);
        for (int j = 0; j < 10; j++) {
            String jAsString = "" + j;
            for (int k = 0; k < oneBits.size(); k++) {
                value.replace(oneBits.get(k), oneBits.get(k) + 1, jAsString);
            }
            if (value.toString().startsWith("0")
                    || !primes.contains(Long.parseLong(value.toString()))) {
                numMisses++;
            }
            if (numMisses > NUM_MISSES) {
                break;
            }
        }
        if (numMisses <= NUM_MISSES) {
            System.out.println("Found with oneBitsForI: " + oneBits);
            return true;
        }

        return false;
    }

    // 000109
    // 111109
    // 222109
    // 333109
    // 444109
    // 555109
    // 666109
    // 777109
    // 888109
    // 999109
}
